package sort;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

/**
 * 思路很简单！
 * 分治思想
 * 虽然简单 但是  细节还是挺多的!
 * 注意不是返回一个新的数组 而是 在原来的数组上直接操作
 */
public class MergeSort {


	
	public static void mergeSort(int arr[]) {
		if(arr == null || arr.length == 1)
			return ;
		int l = 0;
		int r = arr.length - 1;
		process(arr,l,r);
	}
	







	public static void process(int arr[] ,int l,int r) {
		// basecase 
		if(l == r)
			return ;
		int mid = l + r >> 1;
		process(arr,l,mid);
		process(arr,mid + 1,r);
		merge2(arr,l,mid,r);
	}
	
	
	/**
	 * 从始至终 都是 一个数组  arr
	 * 相当于  一个 mid 把 数组 arr 分成两个数组 进行 一个 merge 过程
	 */
	public static void merge(int arr[], int l,int mid,int r) {
		int help[] = new int [r - l + 1];
		int i = 0;
		int temp = mid + 1;
		int left = l;
		while(l <= mid && temp <= r) {
			if(arr[l] <= arr[temp])
				help[i++] = arr[l++];
			else
				help[i++] = arr[temp++];
		}
		while(l <= mid)
			help[i++] = arr[l++];
		while(temp <= r)
			help[i++] = arr[temp++];
		
		// 再将 help 数组 copy 回 arr 数组的相应位置
		i = 0;
		while(left <= r)
		arr[left++] = help[i++];
//		for (i = 0; i < help.length; i++) {
//			arr[left + i] = help[i];
//		}
	}
	
	
	
	
	
	/**
	 * 首先把这个 merge 过程给写出来
	 * 将两个 有序数组合并成一个 有序 数组
	 */
	public static int [] mergePlay(int arr1[] ,int arr2[]) {
		int len1 = arr1.length;
		int len2 = arr2.length;
		int i = 0, j = 0;
		int ans[] = new int [len1 + len2];
		int k = 0;
		while(i < len1 && j < len2) {
			
			/**
			 * 有两种书写方式：
			 * 方式1. 
			 * 把下面的 两个条件语句直接  合并 成一个
			 * if(arr1[i] <= arr[j])
			 * ans[k++] = ans[j++];
			 * 
			 * else
			 *  ans[k++] = ans[j++];
			 *  
			 *  原理都是一样的:
			 */
			
			if(arr1[i] < arr2[j]) {
				ans[k++] = arr1[i++];
			}
			else if(arr1[i] == arr2[j] ) {
				ans[k++] = arr1[i++];
				ans[k++] = arr2[j++];
			}
			else {
				ans[k++] = arr2[j++];
			}
		}
		while(i < len1)
			ans[k++] = arr1[i++];
		while(j < len2)
			ans[k++] = arr2[j++];
		return ans;
	}
	
	
	public static void main(String args[]) {
		int arr1[] = {2,2,3,5};
		int arr2[] = {2,2,4,7};
//		int ans [] = merge(arr1,arr2);
//		System.out.println(Arrays.toString(ans));
		int arr[] = {6,5,4,7,-1,3,2,1};
		mergeSort(arr);
		System.out.println(Arrays.toString(arr));
	}
	
	@Test
	public void testReference() {
		int arr1[] = {2,2,3,5};
		int arr2[] = {2,2,4,7};
	}
	public static void merge2(int nums[],int l,int mid,int r){

		int left = l ,right = mid + 1;

		int helper[] = new int[r - l + 1];
		int index = 0;
		while(left <= mid && right <= r){
			if(nums[left] <= nums[right]){
				helper[index ++] = nums[left++];
			}else{
				helper[index++] = nums[right ++];
			}


		}
		while(left <= mid){
			helper[index++] = nums[left++];

		}
		while(right <= r){
			helper[index++] = nums[right++];
		}
		index = 0;
		for (int i = l; i <= r ; i++) {
			nums[i] = helper[index++];
		}

	}


}
